package com.wyp168.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

/**
 * @ClassName ShortestSubarraySolutino
 * @Title TODO
 * @Description TODO
 * @Author wyp168
 * @Date 2022/10/26 00:22
 */
public class ShortestSubarraySolution {
    public static void main(String[] args) {
        ShortestSubarraySolution solution = new ShortestSubarraySolution();
        int[] nums = {84,-37,32,40,95};
        int k = 167;
        System.out.println(solution.shortestSubarray(nums, k));
    }
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] preSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        int min = n + 1;

        for (int i = 0; i < n + 1; i++) {
            int curPreSum = preSum[i];

            while (!stack.isEmpty() && curPreSum - preSum[stack.peekLast()] >= k) {
                min = Math.min(min, i - stack.pollLast());
            }

            while (!stack.isEmpty() && curPreSum - preSum[stack.peekFirst()] <= 0) {
                stack.pollFirst();
            }

            stack.push(i);
        }

        return min == n + 1 ? -1 : min;

    }
}
